1.5.2 Implementación

La implementación consiste en tomar el diseño del TDA y convertirlo en algo real, en nuestro caso es llevarlo a un lenguaje de computador. La implementación de un TDA no es única; dado un diseño de un TDA es posible implementarlo de muy diversas formas, como se expresa en la figura .

Figure: Un diseño de TDA y sus diversas implementaciones.

Cada implementación puede ser distinta o por los tipos de datos que se utilizan o por los constructores de datos. Esto último se refiere por ejemplo a usar estructuras o clases para construir el TDA. Lo importante aqui, es que, aunque hay varias implementaciones estas representan el mismo TDA. Esto es tan cierto que debe llegarse al caso esquematizado en la figura , una aplicación que usa un implementación de un TDA (una librería) debe ser capaz de cambiar a cualquier otra implementación del TDA (por ejemplo par razones eficiencia) con cambios mínimos.

Figure: Varias implementaciones de un TDA y un uso.

Ahora vamos a reafirmar estos conceptos con el ejemplo, el TDA Complejo que hemos venido trabajando y haremos varias implementaciones de éste, para poder determinar las bondades de cada una y su impacto en un código que utiliza el TDA.

La primera implementación que vamoa a hacer del TDA Complejo consiste en usar un arreglo de dos flotantes, como se ve en la figura ; el de la posición cero se guarda la parte real y en la posición uno la parte imaginaria. Las operaciones se podrián implementar como funciones. Esta implementación se puede ver en el código siguiente:

Figure: El TDA Complejo implementado como arreglo de flotantes.

/*

complejo.c

Autor: "L. Alejandro Bernal R."<lbernal@uvirtual.ean.edu.co>

Descripción: Implementacion del TDA Complejo como un arreglo de flotantes.

*/

#include <stdio.h>

/*

Descripción: Suma dos números complejos.

*/

void sumar(float c1[], float c2[], float respuesta[])

{

        /* Sumar. */

        respuesta[0] = c1[0] + c2[0];

        respuesta[1] = c1[1] + c2[1];

} /* sumar */

int main(void)

{

        float a[2], b[2], resp[2];

        a[0] = 1.0; a[1] = 2.1;

        b[0] = 2.0; b[1] = 3.4;

        sumar(a,b, resp);

        printf("(%f,%f) + (%f,%f) = (%f,%f)\n", a[0], a[1], b[0], b[1], resp[0], resp[1]);

       return 0;

}

Sólo se muestra la función sumar, con ella nos podemos dar cuenta de las principales características de esta implementación. El código es un tanto oscuro porque en él no ve ve el concepto del TDA Complejo y tenemos recordar que la posición cero es la parte real y la posición uno es la parte imaginaria. Se podría mejorar este código utilizando typedef y #define, como se ve en el código que sigue:

/*

complejo.c

Autor: "L. Alejandro Bernal R."<lbernal@uvirtual.ean.edu.co>

Descripción: Implementacion del TDA Complejo como un arreglo de flotantes.

*/

#include <stdio.h>

typedef float Complejo[2]; /* Implementacion como arreglo. */

#define REAL 0

#define IMAG 2

/*

Descripción: Suma dos números complejos.

*/

void sumar(Complejo c1, Complejo c2, Complejo respuesta)

{

        /* Sumar. */

        respuesta[REAL] = c1[REAL] + c2[REAL];

        respuesta[IMAG] = c1[IMAG] + c2[IMAG];

} /* sumar */

int main()

{

        Complejo a, b, resp;

        a[REAL] = 1.0; a[IMAG] = 2.1;

        b[REAL] = 2.0; b[IMAG] = 3.4;

  

        sumar(a,b, resp);

        printf("(%f,%f) + (%f,%f) = (%f,%f)\n", 

                a[REAL], a[IMAG], 

                b[REAL], b[IMAG], 

                resp[REAL], resp[IMAG]);

        return 0;

}

El anterior códigos es una mejora sustancial , puesto que los conceptos se manejan por su nombre y no por número o código que podrían ser difíciles de recordar. Esta idea fué la que originó que aparecieran los lenguajes de alto nivel en contraposición al lenguaje de máquina o el ensamblador que se manejaban numéricamente o con nemonicos. En el primer caso era díficil de recordar qué código correspondía a qué operación, y en el segundo caso, las sintaxis no era natural. Estos son unos de los principios básicos en los TDAs:

Las cosas deben llamarse por su nombre.

Se debe hacer lo que sea más natural.

Lo primero es fácil de entender en especial cuando se piensa que un TDA es un modelo de la realidad, entonces debe haber una correspondencia uno a uno entre la realidad que se está representando y los TDAs. ¿Pero, qué es lo más natural?. Se habla de natural cuando no sólo hay una correspondencia de términos entre la realidad y el TDA (una correspondencia léxica), sino además, cuando hay una correspondencia a niveles sintáctico, semántico y pragmático. Esto es, una correpondencia a nivel de términos, a nivel de como se estructuran y relacionan estos términos y una correpondencia con quienes interpretan y manejan esta realidad.

Pero esta última representación todavia tiene sus problemas, todavía es posible aplicar la función sumar a arreglos de flotantes que no tengan nada que ver con números complejos.

Otra implementación posible del TDA Complejo sería mediante una estructura , como podemos ver en el siguiente código:

/*

complejo2.c

Autor: "L. Alejandro Bernal R."<lbernal@uvirtual.ean.edu.co>

Descripción: Implementacion del TDA Complejo como un struct.

*/

#include <stdio.h>

typedef struct {

   float real; /* Parte real del complejo. */

   float imag; /* parte imaginaria deñl complejo. */

} Complejo;

/*

Descripción: Suma dos números complejos.

*/

void sumar(Complejo *c1, Complejo *c2, Complejo *respuesta)

{

   /* Sumar. */

   respuesta->real = c1->real + c2->real;

   respuesta->imag = c1->imag + c2->imag;

} /* sumar */

int main()

{

   Complejo a, b, resp;

   a.real = 1.0; a.imag = 2.1;

   b.real = 2.0; b.imag = 3.4;

   sumar(&a, &b, &resp);

   printf("(%f,%f) + (%f,%f) = (%f,%f)\n", 

          a.real, a.imag, 

          b.real, b.imag, 

          resp.real, resp.imag);

    return 0;

}

El anterior código es parecido a la segunda versión con arreglos en cuanto a la riqueza expresiva, ganando sólo en que no hay que hacer los dos define que son tan artificiales. Gana más en lo que ya comentamos, ya no es posible sumar dos arreglos de flotantes que no sean complejos, se gana en la verificación de tipos. Aunque esto pudiera no parecer gran cosa en este ejemplo tan pequeño, en un programa grande la mezcla de tipos es una de las grandes fuentes de error y éstos están entre los más difíciles de depurar. Pero hay otro problema, el código no muestra que la operación sumar perteneszca realmente al TDA Complejo. La asociación está unicamente en la mente del programador, el computador no sabe esto realmente. Probemos una nueva implementación esta vez con clases:

/*

complejo3.cpp

Autor: "L. Alejandro Bernal R."<lbernal@uvirtual.ean.edu.co>

Descripción: Implementacion del TDA Complejo como una clase.

*/

#include <stdio.h>

class Complejo {

   private:

   // Atributos:

   float real; /* Parte real del complejo. */

   float imag; /* parte imaginaria deñl complejo. */

    public:

   // Operaciones:

   /*

    Descripción: Construye un complejo.

   */

    Complejo(float r, float i)

    {

      real = r;

      imag = i;

   } // Complejo

   /*

   Descripción: Suma dos números complejos.

   */

   Complejo sumar(Complejo c2)

   {

      return Complejo(real + c2.real, imag + c2.imag);

   } /* sumar */

   /*

   Descripción: Imprime un complejo en salida estandar.

   */

   void imprimir()

   {

      printf("(%f,%f)", real, imag);

   } // impr

}; // class Complejo

int main()

{

   Complejo a(1.0, 2.1), b(2.0, 3.4);

   a.imprimir(); printf(" + "); b.imprimir(); printf(" = ");

   a.sumar(b).imprimir(); 

   printf("\n");

   return 0;

}

En este código la función sumar no solo hace parte del TDA Complejo sino que se gana en varios aspectos:

• Ya es posible retornar una estructura completa cosa que no se podía en C y que hacia necesario declarar la respuesta como un tercer parámetro cuando es más natural que sea el resultado de la función.
• También se gana en consición de notación, por ejemplo en la función sumar no es necesario declarar el primer operando de la suma, es un parámetro implicito, es más, para referirse a sus partes solo es necesario escribir el nombre.
• De otro lado no es necesario pasar los operandos como apuntadores, lo cual no es muy natural y hace que en la funcion main sea necesario ponerle los &, los cuales se pueden olvidar fácilmente.
• En la función main tampoco hay necesidad de las antinaturales asignaciones para inicializar las partes real e imaginaria de cada número complejo esto queda simplemente en la declaración en forma mucho más concisa, claro esto es gracias a que se ha declarado una función de inicialización como un constructor.

Se puede decir entonces que:

La mejor forma de implementación de TDAs son las clases.

Por ello en este libro se seguirá implementando los TDAs utilizando esta forma. A continuación veremos como se usa un TDA.